package com.cqs.leetcode.recursion;

import java.util.LinkedList;
import java.util.Queue;

public class SurroundedRegions130 {

    public void solve(char[][] board) {
        if (board == null || board.length <= 2) return;
        //圈出边界为o的点
        int row = board.length;
        int col = board[0].length;
        //队列保存坐标(通过数组实现)
        Queue<int[]> queue = new LinkedList<>();
        //处理第一行和最后一行
        for (int i = 0; i < col; i++) {
            if (board[0][i] == 'O') queue.add(new int[]{0, i});
            if (board[row - 1][i] == 'O') queue.add(new int[]{row - 1, i});
        }
        //处理第一列和最后一列(四个顶点已经处理过了)
        for (int i = 1; i < row - 1; i++) {
            if (board[i][0] == 'O') queue.add(new int[]{i, 0});
            if (board[i][col - 1] == 'O') queue.add(new int[]{i, col - 1});
        }

        while (queue.size() > 0) {
            //进行标记
            int[] poll = queue.poll();
            int x = poll[0], y = poll[1];
            //表示和边界联通
            board[x][y] = '.';
            //扫描四周是否有'O'和poll点联通
            //上下左右
            if (x - 1 >= 0 && board[x - 1][y] == 'O') {
                queue.add(new int[]{x - 1, y});
            }
            if (x + 1 < row && board[x + 1][y] == 'O') {
                queue.add(new int[]{x + 1, y});
            }
            if (y - 1 >= 0 && board[x][y - 1] == 'O') {
                queue.add(new int[]{x, y - 1});
            }
            if (y + 1 < col && board[x][y + 1] == 'O') {
                queue.add(new int[]{x, y + 1});
            }
        }

        //所有的'O'表示不和外界的'O'联通，可以置为'X'
        for (int i = 0; i < row-1; i++) {
            for (int j = 0; j < col-1; j++) {
                if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
        //所有的'.'表示和外界的'O'联通，还原为'O'
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == '.'){
                    board[i][j] = 'O';
                }
            }
        }

    }
}
